package main.二叉树;

import common.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author tmh
 * @date 2024/7/23 16:49
 * @description
 */
public class T105从前序与中序遍历序列构造二叉树 {
    /**
     * 把这个用deque的方式当作一个模板就行
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //条件判断
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        //用一个栈来辅助
        Deque<TreeNode> deque = new ArrayDeque<>();
        //构造根节点
        TreeNode root = new TreeNode(preorder[0]);
        //把根节点放入deque里面
        deque.push(root);
        //初始化一个遍历中序数组的下标inorderIndex
        int inorderIndex = 0;
        //遍历先序数组，从下标为1开始
        for (int i = 1; i < preorder.length; i++) {
            //获取先序数组里面元素的值
            int preOrderVal = preorder[i];
            //获取栈顶元素
            TreeNode node = deque.peek();
            //如果栈顶元素的值和中序数组里面元素的值不相等，那么就构造左子树，把这个左节点加入到deque里面
            if (node.val != inorder[inorderIndex]) {
                //构造左子树
                node.left = new TreeNode(preOrderVal);
                //把这个左节点加入到deque里面
                deque.push(node.left);
            } else {
                //弹出栈顶元素，移动中序数组下标inorderIndex
                //deque不为空，同时栈顶的元素和中序数组里面的元素相同
                //因为while循环里面在一直往外弹出元素，所以这里的判断就是要用deque.peek().val
                while (!deque.isEmpty() && deque.peek().val == inorder[inorderIndex]) {
                    node = deque.pop();
                    inorderIndex++;
                }
                //构造右子树
                node.right = new TreeNode(preOrderVal);
                //右节点加入deque
                deque.push(node.right);
            }
        }
        return root;
    }
}
